package 算法.leetcode.labuladong.数组和链表;

/**
 * @author lchenglong
 * @date 2022/6/17
 */
public class 使括号有效的最少添加 {
    class Solution {
        public int minAddToMakeValid(String s) {
            // need为对右括号的需求量,res记录插入次数
            int need =0,res = 0;
            for (char c: s.toCharArray()){
                if (c == '('){
                    need++;
                }
                if (c == ')'){
                    need--;
                    // 需要左括号插入
                    if (need == -1){
                        need = 0;
                        res ++;
                    }
                }
            }
            return need +res;
        }
    }
}
